#ifndef _SINGLY_LINKED_LIST_
#define _SINGLY_LINKED_LIST_

#include <stack>
#include <vector>
using namespace std;
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
struct ListNode {
    int       val;
    ListNode* next;
    ListNode( int x ) : val( x ), next( NULL ) {}
};

class SinglyLinkedList {
public:
    // mysolution
    vector< int > reversePrint( ListNode* head ) {

        ListNode* temp = head;

        vector< int > out;

        stack< int > s;

        while ( temp != nullptr ) {
            s.push( temp->val );
            temp = temp->next;
        }
        int n = s.size();
        for ( int i = 0; i < n; i++ ) {
            out.push_back( s.top() );
            s.pop();
        }

        return out;
    }

    // vector
    vector< int > reversePrint2( ListNode* head ) {

        ListNode* temp = head;

        int n = 0;
        while ( temp ) {
            n++;
            temp = temp->next;
        }
        temp = head;
        vector< int > out( n );

        for ( int i = n - 1; i >= 0; i-- ) {
            out[ i ] = temp->val;
            temp     = temp->next;
        }

        return out;
    }

    // recursion :the fastest
    vector< int > reversePrint3( ListNode* head ) {

        if ( head == nullptr ) {
            return {};
        }

        vector< int > out = reversePrint3( head->next );

        out.push_back( head->val );

        return out;
    }

    // mysolution
    ListNode* reverseList( ListNode* head ) {

        if ( head == nullptr || head->next == nullptr ) {
            return head;
        }

        ListNode* first  = head;
        ListNode* second = head->next;
        ListNode* temp;

        first->next = nullptr;

        while ( second != nullptr ) {

            temp         = second->next;
            second->next = first;
            first        = second;
            second       = temp;
        }

        return first;
    }

    // recursion
    ListNode* reverseList2( ListNode* head ) {

        if ( head == nullptr || head->next == nullptr ) {
            return head;
        }

        ListNode* newhead = reverseList2( head->next );
        //! false
        //! newhead->next     = head;
        head->next->next = head;
        head->next       = nullptr;

        return newhead;
    }

    ListNode* getKthFromEnd( ListNode* head, int k ) {

        ListNode* former = head;
        ListNode* latter = head;

        for ( int i = 0; i < k; i++ ) {
            latter = latter->next;
        }
        while ( latter != nullptr ) {
            former = former->next;
            latter = latter->next;
        }
        return former;
    }

    ListNode* deleteNode( ListNode* head, int val ) {

        if ( head->val == val ) {
            return head->next;
        }

        ListNode* p1 = head;
        ListNode* p2 = head->next;
        while ( p2 != nullptr ) {
            if ( p2->val == val ) {
                p1->next = p2->next;
                break;
            }
            p1 = p2;
            p2 = p2->next;
        }

        return head;
    }
    // 剑指 Offer 25. 合并两个排序的链表
    ListNode* mergeTwoLists( ListNode* l1, ListNode* l2 ) {
        if ( l1 == nullptr && l2 == nullptr ) {
            return nullptr;
        }
        else if ( l1 == nullptr ) {
            return l2;
        }
        else if ( l2 == nullptr ) {
            return l1;
        }

        ListNode* p1 = l1;
        ListNode* p2 = l2;

        ListNode* newHead = new ListNode( -1 );
        ListNode* p       = newHead;
        while ( p1 != nullptr && p2 != nullptr ) {
            if ( p1->val > p2->val ) {
                p->next = p2;
                p2      = p2->next;
            }
            else {
                p->next = p1;
                p1      = p1->next;
            }
            p = p->next;
        }

        if ( p1 != nullptr ) {
            p->next = p1;
        }
        if ( p2 != nullptr ) {
            p->next = p2;
        }

        return newHead->next;
    }

    // 将链表小于x的数都放在前面，大于x的数都放在后面，保持原有相对顺序不变
    // 构造一个空的头结点
    ListNode* partition( ListNode* pHead, int x ) {
        ListNode* p = pHead;

        ListNode* newHead = new ListNode( 0 );
        newHead->next     = pHead;
        ListNode* pre     = newHead;

        if ( pHead->val < x ) {
            pre = pHead;
        }

        while ( p && p->next ) {

            if ( p->next->val < x ) {

                ListNode* temp = p->next;
                p->next        = p->next->next;
                temp->next     = pre->next;
                pre->next      = temp;
                pre            = pre->next;
            }
            else {
                p = p->next;
            }
        }
        newHead = newHead->next;
        return newHead;
    }
};

#endif /*_SINGLY_LINKED_LIST_*/